\section{Absolútne bezpečná šifra}

Tento krát sa ideme zaoberať nepodmienenou bezpečnosťou. Uvažujme 
výpočtovo neobmedzene silného útočníka a cypher text only attack (COA).
Požadujeme aby útočník zo znalosti šifrového textu nezískal nič nové.

Označme množinu otvorených textov ako $P$, kľúčov ako $K$, šifrových textov ako $C$
(uvažujeme iba množinu reálne možných šifrových textov). Každému $x \in P$ vieme priradiť
pravdepodobnosť výskytu $pr(x)$, pravdepodobnosť
výskytu konkrétneho kľúča $k \in K$ označíme ako $pr(k)$. Predpokladáme, že
konkrétny kľúc používame iba raz a že jeho voľba nezávisí od otvoreného textu.
Takisto pravdepodobnosť výskytu šifrového textu $c \in C$ označíme $pr(c)$. Táto pravdepodobnosť
bude vždy väčšia ako nula (keďže uvažujeme len šifrové texty, ktoré môžu vzniknúť zašifrovaním).
Všetky tieto množiny považujeme za konečné.

\begin{definicia}
    Šifrovací systém $(E,D)$ je absolútne bezpečný ak:
    $$\forall x \in P, \forall c \in C\colon pr(x | c) = pr(x)$$
\end{definicia}
\begin{komentar}
    Táto definícia vlastne hovorí o tom, že znalosť šifrového textu útočníkovi nepovie nič
    nové, keďže distribúciu pravdepodobnosti otvorených textov pozná.
\end{komentar}

Niekoľko zaujímavých vlastností:
Vzhľadom na to, že dešifrovanie musí byť uskutočniteľné, musí platiť $|C| \geq |P|$.
Ďalej určite platí $|K| \geq |P|$, ináč by sme pri znalosti šifrového textu mohli 
vyskúšať dešifrovanie všetkými kľúčmi a niektoré otvorené texty by sme mohli vylúčiť
($pr(x|c) = 0$). Zaujímavá je situácia keď $|P| = |C| = |K|$, tú popisuje nasledujúca veta:

\begin{veta}{(Shanon)}
    Nech $(E,D)$ je šifrovací systém, kde $|P|=|C|=|K|$. Potom tento šifrovací systém je
    absolútne bezpečný práve vtedy, keď sú splnené nasledujúce vlastnosti:
    \begin{enumerate}
        \item $\forall k \in K\colon pr(k) = \frac{1}{|K|}$
        \item $\forall x \in P, \forall y \in C: \exists! k \in K\colon E_k(x) = y$
    \end{enumerate}
\end{veta}

\begin{dokaz}
    \noindent
    \begin{itemize}
    \item[$\Rightarrow:$] 
        Nech systém $(E,D)$ je absolútne bezpečný.
        Ak by pre $x \in P, y \in C$ neexistoval kľúč $k \in K$ taký, 
        že $E_k(x) = y$, útočník zo znalosti $y$ vie vylúčiť otvorený text $x$,
        čo odporuje tomu, že systém $(E,D)$ je absolútne bezpečný. 
        Keďže $|C|=|K|$, tak tento kľúč môže byť maximálne jeden 
        (keby ich bolo viac, tak by $\exists z \in C$ taký, že
        $x$ nevieme zašifrovať na $z$). 

        Keďže $P$ je konečná, môžeme otvorené texty očíslovať, 
        teda $P = \{ x_1, x_2, \dots, x_n\}$. 
        Teraz fixujme $c \in C$. Pre každý otvorený text musí platiť:
        \begin{equation*}
            pr(x_i) = pr(x_i | c) = \frac{pr(c | x_i) pr(x_i)}{pr(c)}
        \end{equation*}
        a teda
        \begin{equation*}
            pr(c) = pr(c | x_i) = pr(k_i)
        \end{equation*}
        kde $k_i \in K$ je taký kľúč, že platí $E_{k_i}(x_i)=c$. 
        Z toho vyplýva, že všetky kľúče majú rovnakú pravdepodobnosť a keďže
        súčet výskytu ich pravdepodobnosti je $1$, tak 
        $\forall k \in K\colon pr(k) = \frac{1}{|K|}$.

    \item [$\Leftarrow:$]
        Vypočítame $pr(x|c)$ a ukážeme, že definícia platí. Vieme, že:
        \begin{equation*}
            pr(x|c) = \frac{pr(c|x)pr(x)}{pr(c)}
        \end{equation*}
        Ďalej $pr(c|x) = pr(k)$, kde $E_k(x)=c$ a teda 
        $pr(c|x) = \frac{1}{|K|}$. Ešte treba určiť $p(c)$.
        \begin{equation*}
            pr(c) = \sum_{k \in K} pr(k) pr(D_k(c)) = 
                \frac{1}{|K|} \sum_{x \in P} pr(x) = \frac{1}{|K|}
        \end{equation*}
        (Pri dešifrovaní všetkými možnými kľúčmi dostaneme 
        všetky možné otvorené texty (a každý práve raz). 
        A súčet pravdepodobností výskytu všetkých otvorených textov je 1).

        Takže dostávame:
        \begin{equation*}
            pr(x|c) = \frac{pr(c|x)pr(x)}{pr(c)} = 
                \frac{\frac{1}{|K|} pr(x)}{\frac{1}{|K|}} = pr(x)
        \end{equation*}

        A teda systém $(E,D)$ je absolútne bezpečný, čím je náš dôkaz hotový.
    \end{itemize}
\end{dokaz}

\begin{priklad}
    Vernamova šifra je príklad absolútne bezpečného šifrovacieho systému.
\end{priklad}

Iným uhlom pohľadu na absolútne bezpečnú šifru je nerozlíšiteľnosť 2 otvorených textov. 
Teda útočník dostane dva otvorené texty a jeden šifrový text a má určiť, z ktorého otvoreného
textu šifrový text vznikol. Tu nesmie uspieť.

\begin{veta}
    Šifrovací systém $(E,D)$ je absolútne bezpečný práve vtedy, keď:
    \begin{equation*}
        \forall x_1 \in P, \forall x_2 \in P, \forall c \in C
            \colon pr(c|x_1)=pr(c|x_2)
    \end{equation*}
\end{veta}

\begin{dokaz}
    \noindent
    \begin{itemize}
    \item[$\Rightarrow:$] 
        Vieme, že $pr(c|x_1) = \frac{pr(x_1|c) pr(c)}{pr(x_1)}$. 
        Keďže systém $(E,D)$ je absolútne bezpečný, 
        tak $pr(x_1|c) = pr(x_1)$, čiže $pr(c|x_1) = p(c)$. 
        To isté dostaneme aj pre $x_2$.

    \item[$\Leftarrow:$]
        $pr(c|x)$ je rovnaká pre všetky $x \in P$, čiže je konštantná. 
        Nech $pr(c|x) = t$. Potom
        \begin{equation*}
            pr(c) = \sum_{k \in K} pr(k) pr(c|D_k(c)) = 
                t \sum_{k \in K} pr(k) = t
        \end{equation*}
        Čiže $pr(x|c) = pr(x)$, čo sme chceli dokázať.
    \end{itemize}
\end{dokaz}

Takto môžeme podať trochu inú definíciu absolútne bezpečnej šifry.

\begin{definicia}
    Uvažujme kryptoanalytickú hru s nasledovným priebehom:
    \begin{enumerate}
        \item Útočník $A$ pošle druhej strane $B$ dva otvorené texty $p_1, p_2$.
        \item $B$ si zvolí náhodne $b \inr \{0,1\}$
            a náhodný kľúč $k \in K$.
        \item $B\send A: c = E_k(p_b)$.
        \item $A$ sa snaží zistiť z ktorého otvoreného textu $c$ vznikol. 
            Svoj úsudok pošle ako $b'$.
        \item Ak $b' = b$, tak $A$ uspel. V opačnom prípade neuspel.
    \end{enumerate}
    Pokiaľ je systém $(E,D)$ absolútne bezpečný, 
    tak pravdepodobnosť úspechu $A$ je $\frac{1}{2}$.
\end{definicia}

Dá sa ukázať, že tieto dve definície sú ekvivalentné.
\todo{dokaz}
